from typing import List
from collections import defaultdict


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        mem = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                key = "{}*{}".format(word[:i], word[i + 1 :])
                mem[key].append(word)
        print(mem)
        visited = set()

        queue = [beginWord]
        res = 0
        # find = False
        while queue:
            new_queue = []
            for word in queue:
                if word == endWord:
                    return res + 1
                # word = queue.pop()
                for i in range(len(word)):
                    key = "{}*{}".format(word[:i], word[i + 1 :])
                    for search in mem[key]:
                        # print("search", search)
                        if search not in visited:
                            visited.add(search)
                            new_queue.append(search)

            res += 1
            print(new_queue)
            queue = new_queue
        return 0


if __name__ == "__main__":
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    res = Solution().ladderLength(beginWord, endWord, wordList)
    print(res)
